Yao Lirong's Blog

P1019 单词接龙

NOI
2019/06/26

题目来源：洛谷P1019 单词接龙

调了好几天，最后请教了醉神(@magolor)，十分钟给我调好了…

  1. 这个程序一个问题就是循环根本就不会吧dict全循环一遍，那可能就是初始化出了问题： m=pointer 的位置，当时记得应该写一个副本 m 代替 pointer 被改变，但是写着写着忘了 m 具体应该在哪被初始化了，问题就出现在这
  2. 回溯的状态：一定要明确回溯应当回溯到具体那个状态，是ans_temp已经被改变的状态吗？还是未改变的状态？本题中是ans_temp未改变的状态

我的解与标解

  1. 跟我的做法一样，区别只是标解用for循环枚举j而不是跟我一样用直接用dfs函数

下面是我的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
char dict[21][30],ans[500]; int n,vis[21],ans_max=0,ans_temp=0;
void dfs(int,int);
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>dict[i];
    for(int i=1;i<=n;i++) vis[i]=2;
    cin>>dict[0][0];///开头的字母

    dfs(0,0);

    cout<<ans_max;
    return 0;
}
void dfs(int word,int pointer)
{
    if(pointer<strlen(dict[word])){
        ans_temp++;
        int ans_mark=ans_temp;
        ans_max=max(ans_max,ans_temp);

        dfs(word,pointer+1);///这句话以上是将本单词中的下一个字母加入答案字符串中，以下是将查看以这个字母为基准，能不能接上其他单词的龙

        ans_temp=ans_mark;
    }

    int m;
    for(int i=1;i<=n;i++){///枚举n个词中哪个词的首字母可以和现在字符串的最后一个相同
        if(vis[i]>0){
            int j=0;

            ///!!!
            m=pointer;
            ///!!!其他人的做法是直接枚举单词 word 中的所有字母，不像我是通过 dfs(word,pointer+1)来枚举，所以不需要考虑pointer如何如何，我们这里如果对 pointer 后面的字母(pointer+1,pointer+2,...)一个个进行比对，必然会改变pointer的值，所以用了一个副本 m 进行比对，保证pointer值不变

            if(dict[word][m]==dict[i][j]){///如果头一个字母相同
                bool flag=true;
                while(m<strlen(dict[word])){///一直比对到最后一个字母，并且这里判断了“相邻的两部分不能存在包含关系”这一条件
                    if(dict[word][m]!=dict[i][j]) flag=false;
                    m++; j++;
                }
                if(flag){///如果每个字母都一样

                    ///!!!
                    int ans_mark=ans_temp;///记录一下现在的长度，因为再进行其他的dfs，ans_temp会被更新
                    ans_temp+=j-1;///答案字符串的长度就可以加上新加入的单词的长度
                    ///!!!注意这个地方这两句话应该是先记录 ans_temp 再更新 ans_temp ，因为我们最后回溯的时候是要回溯到没有接龙接上当前单词的状态，所以应该是先记录，后更新

                    ans_max=max(ans_max,ans_temp);
                    vis[i]--;

                    dfs(i,j);

                    vis[i]++;
                    ans_temp=ans_mark;///把ans_temp更新回来
                }
            }
        }
    }
}
  1. 先预处理得到两两单词间的最短重合部分，然后搜索得到答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<cstring>
#include<iostream>
#include<cstdio>
using namespace std;
string dict[31]; int ans_now=1,ans_max=0,n,vis[31],overlap[31][31];///这个地方把 ans_now 设为1，是因为第一个开头的字母不会被算在长度内，为了把这个开头的字母算进去，ans_now 从1开始
int find_overlap(string,string);///寻找两个单词的最小重合部分
void dfs(int);
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>dict[i];
    for(int i=1;i<=n;i++) vis[i]=2;
    cin>>dict[0];///开头的字母
    memset(overlap,0,sizeof(overlap));
    for(int i=0;i<=n;i++) for(int j=1;j<=n;j++) 
        overlap[i][j]=find_overlap(dict[i],dict[j]);
    
    dfs(0);
    cout<<ans_max;
    return 0;

}

int find_overlap(string a, string b)///其中，a是将要被别人接上去的字符串，b是想要接上去的字符串
{
    for(int i=a.size()-1;i>=0;i--){///倒序寻找最小重合部分的大小
        int ja=i,jb=0; bool flag=true;
        while(ja<a.size()){///正序看看这个部分是否重合
            if(a[ja]!=b[jb]) {flag=false; break;}
            ja++; jb++;
        }
        if(flag){
            int ans_overlap=a.size()-i; ///得到重叠部分的大小
            if(ans_overlap!=a.size()&&ans_overlap!=b.size()) return ans_overlap; ///判断重叠部分是不是包含部分，如果不是就返回答案
            else if(a.size()==1) return ans_overlap; ///如果是开头的字母(cin>>dict[0])，永远有 ans_overlap==a.size()==0 那么不管ans_overlap!=a.size()是否成立，我们都要返回答案
            else return 0;///其他的情况下，重叠部分是包含部分，不能接龙，所以返回0
        }
    }
    return 0;///没找到重叠部分
}

void dfs(int word)
{
    for(int i=1;i<=n;i++){
        if(overlap[word][i]>0 && vis[i]>0){

            ans_now+=dict[i].size()-overlap[word][i];///接上的字符串的长度
            ans_max=max(ans_max,ans_now);
            vis[i]--;

            dfs(i);

            vis[i]++;
            ans_now-=dict[i].size()-overlap[word][i];
        }
    }
}

Author：Yao Lirong

Link：https://yao-lirong.github.io/blog/P1019%20%E5%8D%95%E8%AF%8D%E6%8E%A5%E9%BE%99/

Publish date：June 26th 2019, 12:00:00 am

Update date：June 27th 2019, 8:39:42 pm

License：本文采用 Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) 进行许可

CATALOG
  1. 1. 我的解与标解
Total : 66
2023
2022
2021
2020
2019
NOI CS2112 Logistics Cornell Review CS3110 Manual Journal Tsinghua Book